package com.cango.student.algorithm.sort;

public class Heap {
    private int[] a; // 数组，从下标 1 开始存储数据
    private int n;  // 堆可以存储的最大数据个数
    private int count; // 堆中已经存储的数据个数

    public Heap(int capicity) {
        a = new int[capicity + 1];
        n = capicity;
        count = 0;
    }

    public void insert(int data) {
        if (count >= n) return; // 堆满了
        ++count;
        a[count] = data;
        int i = count;
        // i/2父节点 本身大于父节点，调换
        while (i/2 > 0 && a[i] > a[i/2]) { // 自下往上堆化
            HeapSort.swap(a, i, i/2); // swap() 函数作用：交换下标为 i 和 i/2 的两个元素
            i = i/2; // 定位到父节点
        }
    }

    public void removeMax() {
        if (count == 0) return; // 堆中没有数据
        a[1] = a[count];
        --count;
        // 自上往下堆化
        HeapSort.heapify(a, count, 1);
    }

}
